package trinnes.oliver.unimaas.smartpentalath.intelligence;

import java.beans.PropertyChangeListener;
import java.beans.PropertyChangeSupport;
import java.util.HashMap;
import trinnes.oliver.unimaas.smartpentalath.control.Game;
import trinnes.oliver.unimaas.smartpentalath.control.Player;
import trinnes.oliver.unimaas.smartpentalath.data.Cell;
import trinnes.oliver.unimaas.smartpentalath.data.Move;
import trinnes.oliver.unimaas.smartpentalath.data.Piece;
import trinnes.oliver.unimaas.smartpentalath.data.Validation;

/**
 * Contains the alpha beta search for finding the optimal move
 * @author Oliver Trinnes
 */
public class Search
{
  private static final int DEPTH_MAX = 20;
  private static final int TIME_LIMIT = 30000;
  private Evaluation evaluation;
  private long startTime;
  private int timeLeft;
  private PropertyChangeSupport changeSupport;
  private int originalDepth;
  private Player player;
  private HashMap<Integer, Integer> killerMoves;

  public Search(Evaluation evaluation)
  {
    this.evaluation = evaluation;
    changeSupport = new PropertyChangeSupport(this);
    killerMoves = new HashMap<Integer, Integer>();
  }

  /*
   * Finds the optimal move, given a restricted time limit
   */
  public int findMaxMove(Game game, Player player)
  {
    this.player = player;
    startTime = System.currentTimeMillis();
    
    /*
     * Initialisation of values for every move.
     * Sorted thoughout the iteration.
     */
    int[][] moveOrdering = new int[61][2];
    for (int i = 0; i < moveOrdering.length; i++)
    {
      moveOrdering[i][0] = i;
      moveOrdering[i][1] = -Evaluation.INFINITY;
    }

    // Iterative deepening until time is up
    for (originalDepth = 0; originalDepth <= DEPTH_MAX; originalDepth++)
    {
      killerMoves.clear();
      
      // Get the alpha beta values for every move
      moveOrdering = getValues(game, moveOrdering, originalDepth);
      
      /*
       * Simple bubble sort for the move ordering because it
       * is called at most 20 times per search.
       * So no performance issues.
       */
      Sort.bubbleSort(moveOrdering);

      // For debugging purposes, nice overview
      printMovesAndValues(moveOrdering, originalDepth);

      // Break if running out of time
      if (noResources())
        break;
    }

    /*
     * This is called when the undo action is called during a computation
     */
    if (player.isNextMoveChanged())
    {
      player.setNextMoveChanged(false);
      return Move.UNDO;
    }

    System.out.println("_______________________________________________________");
    
    // Select first move of the move ordering
    return moveOrdering[0][0];
  }
  
  private int[][] getValues(Game game, int[][] moveOrdering, int depth)
  {
    int maxValue = -Evaluation.INFINITY;
    for (int i = 0; i < moveOrdering.length; i++)
    {
      int move = moveOrdering[i][0];
      if (game.getValidation(move, game.getCurrentPlayer().getPiece()).equals(
              Validation.VALID))
      {
        game.doAction(move, game.getCurrentPlayer());
        int value = -alphaBeta(game, move, depth, maxValue,
                Evaluation.INFINITY, moveOrdering);
        game.doAction(Move.UNDO, game.getCurrentPlayer());

        if (noResources())
          break;

        /*
         * If the time is not up, this iteration is useful,
         * so initialize the new values
         */
        if (i == 0)
          for (int j = 0; j < moveOrdering.length; j++)
            moveOrdering[j][1] = -Evaluation.INFINITY;

        // Save the new value
        moveOrdering[i][1] = value;

        // In oder to miss no prunings, maxValue is used as the initial alpha
        if (value > maxValue)
          maxValue = value;
      }
    }
    return moveOrdering;
  }

  private int alphaBeta(Game game, int move, int depth, int alpha, int beta, int[][] moveOrdering)
  {
    if (noResources())
      return -Evaluation.INFINITY;

    publishTimeLeft();

    if (game.isGameOver() || depth <= 0)
    {
      return evaluation.evaluate(game, move);
    }

    /**
     * Stop search if this cell doesnt have occupied neighbors because it is not
     * a promising move
     */
      boolean onlyEmptyNeighbors = true;
      Cell cell = game.getBoard().getCells().get(move);
      Cell[] neighbors = cell.getNeighbors();
      for (Cell n : neighbors)
        if (n != null && !n.getPiece().equals(Piece.EMPTY))
        {
          onlyEmptyNeighbors = false;
          break;
        }
      if (onlyEmptyNeighbors)
        return Evaluation.INFINITY;
    
    int score = -Evaluation.INFINITY;

    game.switchPlayer();

    /**
     * Lookup killermove
     */
    boolean killerSet = false;
    Integer killerMove = killerMoves.get(depth);
    if (killerMove == null)
      killerMove = -1;
    else
      killerSet = true;

    /**
     * Search children
     */
    for(int i = 0; i<moveOrdering.length; i++)
    {
      int child = moveOrdering[i][0];
      /*
       * If a killermove is available, search it first
       */
      if(killerSet)
      {
        child = killerMove;
        killerSet = false;
        i--;
      }
      // Avoids that the killermove is searched twice
      else if(child == killerMove)
        continue;
      
      // Check validation and search child
      if (game.getValidation(child, game.getCurrentPlayer().getPiece()).equals(
              Validation.VALID))
      {
        game.doAction(child, game.getCurrentPlayer());
        int value = -alphaBeta(game, child, depth - 1, -beta, -alpha, moveOrdering);
        game.doAction(Move.UNDO, game.getCurrentPlayer());

        if (value > score)
          score = value;
        if (score > alpha)
          alpha = score;
        if (score >= beta)
        {
          // Save killer move
          killerMoves.put(depth, child);
          break;
        }
      }
    }

    game.switchPlayer();
    return score;
  }

  public void addPropertyChangeListener(PropertyChangeListener listener)
  {
    changeSupport.addPropertyChangeListener(listener);
  }

  public void removePropertyChangeListener(PropertyChangeListener listener)
  {
    changeSupport.removePropertyChangeListener(listener);
  }

  private void publishTimeLeft()
  {
    int timeLeftNew = (int) ((TIME_LIMIT - System.currentTimeMillis() + startTime)
            / 1000);
    if (timeLeftNew != timeLeft)
    {
      changeSupport.firePropertyChange("new_time_left", timeLeft, timeLeftNew);
      timeLeft = timeLeftNew;
    }
  }

  private boolean noResources()
  {
    return System.currentTimeMillis() - startTime > TIME_LIMIT || player.
            isNextMoveChanged();
  }

  private void printMovesAndValues(int[][] movesAndValues, int depth)
  {
    System.out.println("Depth: " + depth);
    System.out.print("Move:  ");
    for (int a = 0; a < movesAndValues.length; a++)
      System.out.printf("%4d ", movesAndValues[a][0]);
    System.out.println("");
    System.out.print("Value: ");
    for (int a = 0; a < movesAndValues.length; a++)
      System.out.printf("%4d ", movesAndValues[a][1]);
    System.out.println("");
    System.out.println("");
  }

  public Evaluation getEvaluation()
  {
    return evaluation;
  }
  
}
